/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._1008;

/**
 *
 * 返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
 *
 * (回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）
 *
 *  
 *
 * 示例：
 *
 * 输入：[8,5,1,7,10,12]
 * 输出：[8,5,10,1,7,null,12]
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._1008
 * @ClassName: ConstructBinarySearchTree
 * @Author: linyaonan
 * @Date: 2020/1/20 17:33
 */
public class ConstructBinarySearchTree {

    public TreeNode bstFromPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 1; i < preorder.length; i++) {
            int addData = preorder[i];
            build(addData, root);
        }
        return root;
    }

    private TreeNode build(int addData, TreeNode node) {
        if (node != null) {
            if (node.left == null && node.right == null) {
                if (addData > node.val) {
                    node.right = new TreeNode(addData);
                } else {
                    node.left = new TreeNode(addData);
                }
            } else {
                if (addData > node.val) {
                    node.right = build(addData, node.right);
                } else {
                    node.left = build(addData, node.left);
                }
            }
            return node;
        } else {
            return new TreeNode(addData);
        }
    }

}
